学习笔记： Reinforcement Learning: An Introduction, Richard S. Sutton and Andrew G. Barto c 2014, 2015, 2016

数学符号看不懂的，先看看这里：

时序差分学习结合了动态规划和蒙特卡洛方法，是强化学习的核心思想。

时序差分这个词不好理解。改为当时差分学习比较形象一些 - 表示通过当前的差分数据来学习。

蒙特卡洛的方法是模拟（或者经历）一段情节，在情节结束后，根据情节上各个状态的价值，来估计状态价值。 时序差分学习是模拟（或者经历）一段情节，每行动一步（或者几步），根据新状态的价值，然后估计执行前的状态价值。 可以认为蒙特卡洛的方法是最大步数的时序差分学习。 本章只考虑单步的时序差分学习。多步的时序差分学习在下一章讲解。

数学表示 根据我们已经知道的知识：如果可以计算出策略价值（\pi状态价值v_{\pi}(s)，或者行动价值q_{\pi(s, a)}），就可以优化策略。 在蒙特卡洛方法中，计算策略的价值，需要完成一个情节(episode)，通过情节的目标价值G_t来计算状态的价值。其公式： Formula MonteCarlo V(S_t) \gets V(S_t) + \alpha \delta_t \\ \delta_t = [G_t - V(S_t)] \\ where \\ \delta_t \text{ - Monte Carlo error} \\ \alpha \text{ - learning step size}

时序差分的思想是通过下一个状态的价值计算状态的价值，形成一个迭代公式（又）： Formula TD(0) V(S_t) \gets V(S_t) + \alpha \delta_t \\ \delta_t = [R_{t+1} + \gamma\ V(S_{t+1} - V(S_t)] \\ where \\ \delta_t \text{ - TD error} \\ \alpha \text{ - learning step size} \\ \gamma \text{ - reward discount rate}

注：书上提出TD error并不精确，而Monte Carlo error是精确地。需要了解，在此并不拗述。

本章介绍的是时序差分学习的单步学习方法。多步学习方法在下一章介绍。

单步时序差分学习方法TD(0)

多步时序差分学习方法

单步时序差分学习方法

多步时序差分学习方法

Q-learning 算法（Watkins, 1989）是一个突破性的算法。这里利用了这个公式进行off-policy学习。 Q(S_t, A_t) \gets Q(S_t, A_t) + \alpha [R_{t+1} + \gamma \underset{a}{max} \ Q(S_{t+1}, a) - Q(S_t, A_t)]

单步时序差分学习方法

单步时序差分学习方法

考虑到重要样本，把\(\rho\)带入到Sarsa算法中，形成一个off-policy的方法。 \rho - 重要样本比率(importance sampling ratio) \rho \gets \prod_{i = \tau + 1}^{min(\tau + n - 1, T -1 )} \frac{\pi(A_t|S_t)}{\mu(A_t|S_t)} \qquad \qquad (\rho_{\tau+n}^{(\tau+1)})

多步时序差分学习方法

Tree Backup Algorithm的思想是每步都求行动价值的期望值。 求行动价值的期望值意味着对所有可能的行动\(a\)都评估一次。

多步时序差分学习方法

时序差分学习方法的限制：学习步数内，可获得奖赏信息。 比如，国际象棋的每一步，是否可以计算出一个奖赏信息？如果使用蒙特卡洛方法，模拟到游戏结束，肯定是可以获得一个奖赏结果的。